// https://leetcode.cn/problems/nth-magical-number/
// Created by ade on 2022/11/22.
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:

    int nthMagicalNumber(int n, int a, int b) {
        int MOD = 1e9 + 7;
        long long left = min(a, b);
        long long right = left * n;
//        int c = a * b / __gcd(a, b); // 最小公倍数
        int c = lcm(a, b); // 最小公倍数 since c++17
        long long mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            int cnt = mid / a + mid / b - mid / c;
            if (cnt >= n) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right % MOD;
    }
};

int main() {
    Solution so;
    cout << so.nthMagicalNumber(3, 6, 4) << endl;
    return 0;
}